When we've seen this issue it's usually been saved credentials in Windows credential manager. For some reason they can authenticate but then Outlook randomly tries the credentials in credential manager. If the credentials are old you will get a login prompt. That's always the first thing I check.